package cn.chen.算法.查找;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 二分查找（递归形式）
 */
public class BinarySearch {

    public static void main(String[] args){

        int [] arr={1,5,9,41,41,41,41,52,63,91};
        int index = binarySearch(arr, 41, 0, arr.length-1);
        if(index==-1)
            System.out.println("没有找到该元素");
        else
            System.out.println(arr[index]);

        List<Integer> list = binarySearchAll(arr, 41, 0, arr.length-1);

        if(list!=null) {
            for (Integer i : list) {

                System.out.println(arr[i]);
            }
        }
        else
            System.out.println("没有该元素");
    }

    /**
     *
     * @param arr   被查询的数组
     * @param value 要查询的数值
     * @param head  要查询的前区间
     * @param end   要查询的后区间
     * @return      返回值就是查询到的值的索引
     */
    public static int binarySearch(int[] arr,int value,int head,int end){

        int index=-1;
        if(head<=end){

            int min=(head+end)/2;
            if(arr[min]>value)  // 就去查询min前面的数组了

                index=binarySearch(arr,value,head,min-1);
            else if(arr[min]<value) // 就去查找min后面的数组了

                index=binarySearch(arr,value,min+1,end);
            else
                index=min;
        }
        return index;
    }

    /**
     *
     * @param arr
     * @param value
     * @param head
     * @param end
     * @return      返回值就是查询的该值的所有索引
     */
    public static List<Integer> binarySearchAll(int[] arr, int value, int head, int end){

        List<Integer> index=null;

        if(head<=end){

            int min=(head+end)/2;
            if(arr[min]>value)  // 就去查询min前面的数组了
                index=binarySearchAll(arr,value,head,min-1);
            else if(arr[min]<value) // 就去查找min后面的数组了
                index=binarySearchAll(arr,value,min+1,end);
            else{   // 要找到数据中相同的全部的值，就需要找到一个之后对该索引前后分别进行递归，然后查找

                index=new ArrayList<>();
                index.add(min); // 将索引添加到集合中

                int temp=min;
                while(arr[--temp]==value)   // 往min前面遍历，直到遍历到不是要查找的值
                    index.add(temp);

                temp=min;
                while (arr[++temp]==value)  // 往min后面遍历，直到遍历到不是要查找的值
                    index.add(temp);
            }
        }
        return index;
    }
}
